The present invention relates to computer programming and more specifically to systems for checking computer programs.
Currently, program development is generally accomplished within a programming environment which contains multiple development tools. One example of a programming environment is the Visual C++ programming environment as distributed by the Microsoft Corporation, Redmond, Wash. A programmer may use the environment to create a workspace which links together multiple files of a program, to compile the program using the environment""s compiler, and to debug the program using the environment""s debugger. Even though these tools exist, the programer must keep track of the various connections between variables, classes, procedures and structures within the code and identify any discrepancies to have the program execute. Typically, the tracking must be done manually without the assistance of the development environment.
Even if a program is executable and is executed on a computer, the program still may not function correctly. In order to determine whether a program is producing correct internal results and a correct final output, the programmer must keep track of the flow of data between various components of the code for the program and analyze the results. If a function passes a variable to another process within the program and the variable does not contain an acceptable value, the end data may be faulty. The programmer must then determine where the error is located and what caused the error. A modification by a programmer to a single variable may affect multiple and disjointed lines of code producing errors that may be difficult to trace manually. Additionally, if the programmer chooses to move or change an element of code, the programmer must again manually track the relationships that are changed throughout the program by the modification.
The present invention solves the problems of the prior art by providing a method and apparatus for structuring a program segment. In a first embodiment of the method for use with a computer having memory, for structuring a program segment, the method begins with the step of identifying a series of program blocks in the segment. Each block is a functional piece of code in the segment and has at least one point corresponding to at least one of entry and exit, in such a manner that the entire segment is divided into blocks with each block being situated in an execution path along which the segment executes in a downstream direction. With respect to each block, a block representative is associated for allocating computer memory for data elements that are needed for the associated block to execute. The block representative assigns a value to any data element required by the associated block to have a value. The block representative also calls the associated block for execution, receives return of control after execution of the block, and passes control based on available data. In another embodiment of the method, a block of interest is treated as a sub-segment. In the sub-segment a series of program sub-blocks are identified in the block. Each sub-block is a functional piece of code in the block and has at least one point corresponding to at least one of entry and exit, in such a manner that the entire block is divided into sub-blocks with each sub-block being situated in an execution path along which the block executes in a downstream direction. With respect to each sub-block, a sub-block representative is associated with the sub-block. The sub-block representative allocates computer memory for data elements that are needed for the associated sub-block to execute. The sub-block representative assigns a value to any data element required by the associated sub-block to have a value. The sub-block representative calls the associated sub-block for execution, receives return of control after execution of the sub-block, and passes control based on available data.
In another embodiment of the method, the block representative includes a virtual page, where the virtual page is a virtual entry page when associated with an entry point and the virtual page performs the functions of allocating computer memory for data elements that are needed for the associated sub-block to execute, assigning a value to any data element required by the associated sub-block to have a value and calling the associated sub-block for execution of the block representative. The virtual page is a virtual exit page when associated with an exit point and the virtual page performs the functions of receiving return of control after execution of the sub-block, and passing control based on available data.
In yet another embodiment of the method, the block representative also validates all data elements that are assigned values by the associated block. In the step of assigning a value to any data element required by the associated block to have a value, the step includes evaluating expressions that depend on data elements created by upstream block representatives.
In still yet another embodiment of the method, in the step of passing control based on available data, the step includes executing a decision to identify a downstream block to be executed next by evaluating an expression that depends on data elements created by an upstream block representative or by the associated block itself.
In another embodiment, of the method for each given virtual entry page, all data elements are identified, from upstream virtual pages, on which the data elements of the given virtual entry page are logically dependent. Any upstream pages containing such data elements are considered ancestor pages. Any given entry page may lie in any number of execution paths and each data element of the given entry page is expressed as a function of one or more data elements occurring in one or more ancestor pages along any of the execution paths.
In a further embodiment of the method, for each virtual entry page, the method includes the step of determining with respect to each data element appearing in any of the expressions whether such data element has been created in an upstream virtual page. The method may also include the step of identifying inconsistent virtual entry pages. Pages are identified as inconsistent if the page includes a data element that is logically dependent on a data element that does not appear in an ancestor page.
In another embodiment, the method may identify a block as inconsistent if the block is associated with a virtual entry page that is identified as inconsistent.
Where the software program includes a loop, so that in execution a given point is passed more than once, and where in determining whether a given page is upstream of another page, a page is indexed according to the number of times that it occurs in execution of the program. A page of a first index is regarded as upstream of the same page of an index greater than the first index. After at least one occurrence of the loop, each data element of the given entry page is expressed as a function of one or more data elements occurring only in a predetermined number of ancestor pages in previous iterations of the loop.
In a case wherein a block is modified in such a way as to require a modification in a virtual exit page associated with the block, the method identifies all data elements, in downstream entry pages, that are affected by the modification. Similarly in a case wherein a block is modified in such a way as to require a modification in a virtual entry page associated with the block, upstream pages are examined to identify any data element, in the virtual entry page, that lacks a logical dependency on one or more data elements occurring in one or more ancestor pages.
Where a block is subject to a move from its current position within the segment to a new position within the segment, the method identifies all downstream entry pages that are affected by the move and all upstream exit pages are checked to identify whether as a result of the move there are any data elements associated with the virtual entry page for the block that are not available from an upstream exit page so that logical consistency may be maintained. If a block is subject to a move from its current execution path within the segment to a new execution path within the segment, all downstream entry pages are identified in the new execution path that are affected by the move and all upstream exit pages are checked in the new execution path to identify whether as a result of the move there are any data elements associated with the virtual entry page for the block that are not available from an upstream exit page so that logical consistency may be maintained.
In another embodiment, a function defines the dependency of a given data element of the given entry page based on one or more data elements occurring in one or more ancestor pages. The method also assigns a sense to a selected set of data elements occurring in virtual pages of the segment and to a selected set of functions, which affect the selected set of data elements, that are implemented in the segment. It is then determined whether the function, applied to the one or more data elements occurring in one or more ancestor pages, has a sense that is compatible with the sense of the data element of the given entry page or a superset of the sense of the data element of the given entry page. Data elements represented by an identical data structure are assigned the same sense and have an identical set of data validation rules. The senses of the one or more data elements may be arranged into hierarchical levels so that data elements having the same sense level or a higher sense level are compatible and higher sense levels are a superset of lower sense levels.
In an embodiment of the apparatus for identifying inconsistencies in a software program the apparatus includes a block registrar module, a routing map module, a decision expert module and a data transfer expert. The block registrar module identifies a series program blocks constituting a segment. The segment is at least a part of the program where each block has at least one point corresponding to at least one of entry and exit. The routing map module is coupled to the block registrar module and sequences the blocks along a program execution path in which the program executes in a downstream direction. The decision expert module is coupled to the routing map module and determines which execution path to follow when execution path junctions occur. The data transfer expert is coupled to the decision expert module and defines and associates a block representative with respect to each block. The block representative allocates computer memory for data elements that are needed for the associated block to execute, assigns value to any data element required by the associated block to have a value, calls the associated block for execution, receives return of control after execution of the block, and passes control based on available data.
In a further embodiment of the apparatus, a consistency checker module coupled to the data transfer module is included. The consistency checker module, for each given block representative, identifies all data elements, from upstream block representatives, on which the data elements of the given block representative are logically dependent. In another embodiment of the apparatus, a code generator module is included. The code generator module generates executable code based on the blocks after the blocks are found to be consistent.
In another related embodiment of the apparatus the block representative includes a virtual page. The virtual page is a virtual entry page when associated with an entry point and performs the functions of defining and allocating computer memory for data elements that are needed for the associated block to execute, assigning a value to any data element required by the associated block to have a value, and calling the associated block for execution. The virtual page is a virtual exit page when associated with an exit point and performing the functions of receiving return of control after execution of the block, and passing control based on available data. Where the software program includes a loop, so that in execution a given point is passed more than once, the data transfer expert module indexes a page according to the number of times that it appears in execution of the program. The consistency checker module reports a page of a first index as upstream of the same page of an index greater than the first index. For a given entry page in an execution path after at least one occurrence of the loop, each data element of the given entry page is logically dependent, if at all, on one or more data elements occurring only in a predetermined number of ancestor pages in previous iterations of the loop.
The consistency checker module may further include a modification checker component. If a block is modified in such a way as to require a modification in a virtual exit page associated with the block, the modification checker component uses the result to identify all data elements, in downstream entry pages, that are affected by the modification.
If a block is modified in such a way as to require a modification in a virtual entry page associated with the block, the modification checker component uses the result to examine upstream pages to identify any data element, in the virtual entry page, that lacks a logical dependency on one or more data elements occurring in one or more ancestor pages. If a block is subject to a move from its current position within the segment to a new position within the segment, the modification checker component uses the result to identify all downstream entry pages that are affected by the move. If a block is moved from its current position within the segment to a new position within the segment, the modification checker component uses the result to identify all downstream entry pages that are affected by the move and checks all upstream exit pages to identify whether as a result of the move there are any data elements associated with the virtual entry page for the block that are not available from an upstream exit page so that logical consistency may be maintained. If a block is moved from its current execution path within the segment to a new execution path within the segment, the modification checker component uses the result to identify all downstream entry pages in the new execution path that are affected by the move and to check all upstream exit pages in the new execution path to identify whether as a result of the move there are any data elements associated with the virtual entry page for the block that are not available from an upstream exit page so that logical consistency may be maintained. If a block is moved from its current execution path within the segment to a new execution path within the segment, the modification checker component uses the result to identify all downstream entry pages that are affected in the current execution path by the move to the new execution path and to check all upstream exit pages in the current execution path to identify whether as a result of the move to the new execution path there are any data elements associated with the virtual entry page for the block that are not available from an upstream exit page so that logical consistency may be maintained.
In yet another embodiment, the consistency checker module further includes a formula consistency component. The formula consistency component assigns a sense to a selected set of data elements occurring in virtual pages of the segment and to a selected set of functions, which affect the selected set of data elements, that are implemented in the segment. The formula consistency component also determines whether the function, applied to the one or more data elements occurring in one or more ancestor pages, has a sense that is compatible with the sense of the data element of the given entry page or a superset of the sense of the data element of the given entry page. The formula consistency component may assign the same sense to data elements that are represented by an identical data structure and uses, with respect to such data elements, an identical set of data validation rules. The formula consistency component may also arrange the senses of the one or more data elements into hierarchical levels so that data elements that have the same sense level or a higher sense level are compatible and higher sense levels are a superset of lower sense levels.